size = 30
iter = 50


def makeboard(x=0.0):
	board = []
	for i in range(size):
		board.append([x] * size)
	return board;
	
neighborCount=makeboard();
for i in range(size):
	for j in range(size):
		neighborCount[i][j]=4.0;
		if(i==0 or j==0 or i==size-1 or j==size-1):
			neighborCount[i][j]=3.0;
			if( i==j or i+j==size-1):
				neighborCount[i][j]=2.0;
				

def perform(prev, nex):
	for i in xrange(size):
		for j in xrange(size):
			nex[i][j]=0.0;
			if( i>0 ): #left neighbor
				nex[i][j]+=prev[i-1][j]/neighborCount[i-1][j];
		
			if( i<size-1): #right neighbor	
				nex[i][j]+=prev[i+1][j]/neighborCount[i+1][j];
			
			if( j>0 ): #top neighbor
				nex[i][j]+=prev[i][j-1]/neighborCount[i][j-1];
			
			if( j<size-1 ): #bottom neighbor
				nex[i][j]+=prev[i][j+1]/neighborCount[i][j+1];
				
tmpboard1=makeboard();
tmpboard2=makeboard();

def getconfig(x, y):

	board=tmpboard1
	for i in xrange(size):
		for j in xrange(size):
			board[i][j]=0.0;
	board[x][y] = 1.0;
	nex=tmpboard2;

	# perform 50 iterations on the board
	for i in xrange(iter):
		perform(board,nex);
		tmp=board;
		board=nex;
		nex=tmp;

	return board;

def flipXAxis(board):
	for i in xrange(size / 2):
		for j in xrange(size):
			tmp=board[i][j];
			board[i][j]=board[size-1-i][j];
			board[size-1-i][j]=tmp;
	return board;

def flipYAxis(board):
	for i in xrange(size):
		for j in xrange(size / 2):
			tmp=board[i][j];
			board[i][j]=board[i][size-1-j];
			board[i][size-1-j]=tmp;
	return board;

def printBoard(board):
	for row in board:
		print row;

def euler213():
	board=makeboard(1.0);
	
	for i in xrange(size / 2):
		for j in xrange(size / 2):
			print "cell %d, %d" % (i,j);
			fleaboard=getconfig(i,j);
			for x in xrange(size):
				for y in xrange(size):
					board[x][y]*=1.0-fleaboard[x][y];
			flipXAxis(fleaboard);
			for x in xrange(size):
				for y in xrange(size):
					board[x][y]*=1.0-fleaboard[x][y];
			flipYAxis(fleaboard);
			for x in xrange(size):
				for y in xrange(size):
					board[x][y]*=1.0-fleaboard[x][y];
			flipXAxis(fleaboard);
			for x in xrange(size):
				for y in xrange(size):
					board[x][y]*=1.0-fleaboard[x][y];
	printBoard(board);
	evalue=0;
	for i in xrange(size):
		for j in xrange(size):
			evalue+=board[i][j];
		
	return evalue;


print euler213();

